Various arbitration schemes, for use is allocating a limited resource to multiple clients, are known in the art. Some arbitration schemes introduce some randomness in the arbitration process, and are therefore referred to as “random arbitration.” Known random arbitration schemes, however, tend to be computationally-intensive, and therefore have limited scalability. Moreover, random arbitration are often problematic in terms of maintaining fairness and preventing starvation.